蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Binary Tree Zigzag Level Order Traversal

发表于 更新于 分类于 阅读次数： Valine：

题目大意

按之字形遍历二叉树（一正一反）

解题思路

来自：链接

解题思路：这道题和上一题层序遍历那道题差不多，区别只是在于奇数层的节点要翻转过来存入数组。
代码：

代码

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def zigzagLevelOrder(self, root):
        tree = []
        if not root:
            return tree
        curr_level = [root]
        direction = 'L'
        # print(type(root), type(curr_level))  # (<class 'precompiled.treenode.TreeNode'>, <type 'list'>)
        # print(curr_level)  # 作为list，却并不能遍历整个树
        while curr_level:
            level_list = []
            next_level = []
            for temp in curr_level:
                level_list.append(temp.val)
                if temp.left:
                    next_level.append(temp.left)
                if temp.right:
                    next_level.append(temp.right)
            if direction == 'L':
                tree.append(level_list)
                direction = 'R'
            else:
                tree.append(level_list[::-1])
                direction = 'L'
            curr_level = next_level
        return tree

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of lists of integers
    def preorder(self, root, level, res):
        if root:
            if len(res) < level+1: res.append([])
            if level % 2 == 0: res[level].append(root.val)
            else: res[level].insert(0, root.val) # 向0位置插入
            self.preorder(root.left, level+1, res)
            self.preorder(root.right, level+1, res)
    def zigzagLevelOrder(self, root):
        res=[]
        self.preorder(root, 0, res)
        return res

总结

  1. insert()方法语法：
    list.insert(index, obj)
    参数
    index – 对象 obj 需要插入的索引位置。
    obj – 要插入列表中的对象。
  2. tree.append(level_list[::-1])将数组倒序插入